package leetcode_800;

/**
 *@author 周杨
 *MaxChunksToMakeSortedII_768 数组里有重复的 问最大能用多少个块排序
 *describe:用标记数组 标记右边最大的 AC 41% 
 *2018年10月19日 下午1:32:49
 */
public class MaxChunksToMakeSortedII_768{
	public int maxChunksToSorted(int[] arr) {
		int n = arr.length;
		int[] minOfRight = new int[n];//当前遍历的值 一定不能超过最右的边界 且要合法
		minOfRight[n - 1] = arr[n - 1];
		for (int i = n - 2; i >= 0; i--) {
			minOfRight[i] = Math.min(minOfRight[i + 1], arr[i]);
		}
		int res = 0;
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < n - 1; i++) {
			max = Math.max(max, arr[i]);
			if (max <= minOfRight[i + 1])
				res++;
		}
		return res + 1;
	}
}
